#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <vector>
#include <queue>
#include <functional>
#include <unistd.h>
#include <algorithm>

using namespace std;

#define TOPK_NUM 3
#define MAX_NUM 10

// 快排分割解决topk问题
// 1、取数组中任意一个元素作为基准值，将数组分割成小于基准值和大于基准值的两部分
// 2、若基准值的下标为k-1，则基准值即为第k大的元素，否则，若基准值的下标小于k-1，
// 则第k大的元素在大于基准值的部分，否则在小于基准值的部分
// 3、递归分割，直到基准值的下标为k-1，此时基准值即为第k大的元素

// 快排分割理论上时间复杂度为O(n)，最坏情况下为O(n^2)
// 每次分割时，若数组长度为n，理想情况下每次分割n/2

int partition(vector<int> &vec, int left, int right)
{
    int pivot = vec[left]; // 选取第一个元素作为基准值
    // left < right 保证分割时，left和right不会越界
    while (left < right) {
        // 从右向左找到第一个小于基准值的元素，并将右值赋值给左值
        // 如果没找到就一直移动右边下标，直到left = right
        while (left < right && vec[right] >= pivot) right--;
        vec[left] = vec[right];
        // 从左向右找到第一个大于基准值的元素，并将左值赋值给右值
        // 如果没找到就一直移动左边下标，直到left = right
        while (left < right && vec[left++] <= pivot) left++;
        vec[right] = vec[left];
    }
    // 将基准值赋值给分割后的位置
    vec[left] = pivot;
    return left; // 返回基准值的下标
}

void selecttopk(vector<int> &vec, int left, int right, int k)
{
    int pos = partition(vec, left, right);
    if (pos == k - 1)
    {
        cout << "the " << k << " topk number is: " << vec[pos] << endl;
        return;
    }

    else if (pos < k - 1)
    {
        selecttopk(vec, pos + 1, right, k);
    }

    else
    {
        selecttopk(vec, left, pos - 1, k);
    }
}

int main()
{
    srand(time(NULL));
    // vector 为动态数组，可以动态添加元素，但是push_back()是尾插
    vector<int> vec;
    for (size_t i = 0; i < MAX_NUM; i++)
    {
        vec.push_back(rand() % MAX_NUM);
        cout << vec[i] << " ";
    }
    cout << endl;
    cout << "selecttopk :" << endl;
    selecttopk(vec, 0, vec.size() - 1, TOPK_NUM);
    for (size_t i = 0; i < TOPK_NUM; i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    return 0;
}